package zuoshen_mid.class1.skill3_dataPreprocess;

import org.junit.Test;

import zuoshen_mid.class1.extra_rand.RandM_N;

/* 
    将格子染色为左边全是G，右边全是R的形式，最少的染色数
*/
public class GridColoring {
    
    public int minColoring1(String grid) {
        /* 
            以当前格子为界，左边（不包括自己）染为G，右边（包括）染为R
        */
        int res = Integer.MAX_VALUE;
        for (int i = 0; i <= grid.length(); i++) {
            int left = countLeftR(grid, i - 1),
            right = countRightG(grid, i);
            res = Math.min(res, left + right);
        }
        return res;
    }

    public int countLeftR(String s, int idx) {
        int count = 0;
        for (int i = idx; i >= 0; i--) {
            if (s.charAt(i) == 'R') count++;
        }
        return count;
     }
    public int countRightG(String s, int idx) {
        int count = 0;
        for (int i = idx; i < s.length(); i++) {
            if (s.charAt(i) == 'G') count++;
        }
        return count;
     }
        
     /* 
        缓存下左的R，右边的G，便于查表而不是遍历
     */
    public int minColoring(String grid) {
        int res = Integer.MAX_VALUE, len = grid.length();
        int[] leftR = new int[len + 1], 
        rightG = new int[len + 1];
        leftR[0] = 0;
        for (int i = 1; i <= len; i++) {
            leftR[i] = leftR[i - 1];
            leftR[i] += grid.charAt(i - 1) == 'R' ? 1 : 0;
        }
        rightG[len] = 0;
        for (int j = len - 1; j >= 0; j--) {
            rightG[j] = rightG[j + 1];
            rightG[j] += grid.charAt(j) == 'G' ? 1 : 0;
        }
        for (int i = 0; i <= len; i++) {
            res = Math.min(res, leftR[i] + rightG[i]);
        }
        return res;

    }


    @Test
    public void test() {
        RandM_N mn = new RandM_N();
        for (int i = 0; i < 1000; i++) {
        String g = "";
        for (int j = 0; j < 20; j++) {
            g += (mn.rand01() == 0) ? "R" : "G";
        }
        System.out.print(minColoring1(g));
        System.out.print("=====");
        System.out.print(minColoring(g));
        System.out.println();
        }
    }
}
